/*-
 * HuffmanProcessor.java
 *
 * $LastChangedBy: stein $
 * $LastChangedRevision: 95 $
 * $LastChangedDate: 2007-02-13 16:19:24 +0000 (Tue, 13 Feb 2007) $
 * $HeadURL: svn://localhost/SMS/src/com/googlecode/attention/sms/comp/HuffmanProcessor.java $
 *
 * Copyright (c) 2007, Stein Gunnar Bakkeby
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of Stein Gunnar Bakkeby nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.googlecode.attention.sms.comp;

import static com.googlecode.attention.sms.comp.CompressionProcessor.*;
import static com.googlecode.attention.util.SMSCharacterSet.*;
import static com.googlecode.attention.util.UtilLogStatements.UTIL_DEBUG;

import java.io.File;
import java.io.IOException;
import java.io.FileOutputStream;

import java.util.ArrayList;

import com.googlecode.attention.io.CSVReader;
import com.googlecode.attention.io.CSVWriter;
import com.googlecode.attention.sms.pdu.CBS;
import com.googlecode.attention.util.Convert;
import com.googlecode.attention.util.IntArrayBuilder;
import com.googlecode.attention.util.Settings;

/** * Huffman coding. * <BR> * <BR>Huffman encoding requires the set of characters that may be encoded * to be represented within a binary tree structure. The tree is constructed * of "nodes" which have the following properties: * <BR> * <BR> - A Parent node. A node that has no parent is the "root" node. * <BR> - Up to 2 Child nodes. A node that has no children is a "leaf" node. * <BR> - Character value. If the node is a leaf node it represents a *        character represented within the tree. * <BR> - Weight. If the node is a leaf node, the weight is the frequency *        with which the associated character has occurred in the input stream. *        Otherwise the weight is simply the sum of the weights of the nodes *        children. * <BR> * <BR>Typically, a tree will be implemented as an array of node structures * and parent / child details for a given node will be represented by the index * of the appropriate node within the array. Every node in the tree (except the * root node or in the case where the tree contains just a single leaf node) * has a "sibling" - the other node that shares the same parent node. * <BR> * <BR>For the binary tree to be a Huffman tree its construction needs to * display a further property. This is that the nodes can be listed in * ascending order of weight and in so doing every node is adjacent to its * sibling in the list. This property needs to be preserved at all times -  * when the tree is initially created, when a new leaf node is added to the * tree to represent a new character and when the frequency of a leaf node * is incremented as a new instance of that character is processed. * <BR> * <BR>The ordering of nodes is also significant in that it will determine * which of the siblings is the "left-hand" as opposed to "right-hand" of the * sibling pair. Encoding a symbol involves navigating the tree from leaf to * root and emitting a bit to the encoded stream the value of which depends * on whether the current node is the left or right hand sibling. If the node * is a left hand node, the bit value is 0 and if it is a right hand node, * the bit value is 1. Assuming that the 1st element of the array of nodes has * an index value of 0, this means that left hand nodes will have even * numbered indices and right hand nodes will have odd numbered indices. * <BR> * <BR>Node weights are assumed to be 16 bit unsigned values and this means * that the potential exists for these values to overflow. To handle this * case, the algorithm defines a maximum weight value for the root node. If * this is to be exceeded, the weights of all leaf nodes are divided by 2 and * the tree is rebuilt. The maximum value for the root weight is defined to be * 8000 (hex). * <BR> * <BR>Although the bit sequence representing the encoded symbol is discovered * in the order of traversing the tree from leaf to root, for decoding the bit * sequence needs to be processed in the order that describes the navigation * of the tree from root to leaf. Thus the entire encoding bit sequence needs * to be collected in some temporary variable and emitted to the output stream * in reverse order. For example if the passage from leaf to root is described * by the sequence 010011, the bits added to the output stream would be 110010. * The need to collect the bits in a temporary variable also introduces the * potential for this value to overflow. Given the maximum value for the root * node weight described above, a 32bit variable is suitable of containing all * possible bit sequences. * <BR> * <BR>If a symbol that does not already exist in the tree is to be encoded, * either the "New 7bit Character" or the "New 8bit Character" is encoded, the * lower 7 bits of the new character value are then added literally to the out * put stream and the new character needs to be added to the tree. This is done * by splitting the "lightest" node (the first node in the list ordered by * ascending weight) such that it becomes a parent node whose right hand child * is the leaf node that was originally represented by the node being split and * the left hand child is a new leaf node representing the new character. The * new leaf is initially created with a weight of 0 but this is immediately * updated as described below. * <BR> * <BR>If a new symbol has been added to the tree or a new instance of an * existing symbol processed, the weight for the associated leaf node needs to * be incremented and the tree updated to preserve the "sibling" property. The * tree is updated in the following manner. If the node a position x in the * ascending weight ordered list has had its weight incremented by 1, the list * needs to be scanned from position x in ascending weight order to identify * the node at position y such that the node at position (y+1) is the first * node encountered that has a weight greater than or equal to the new weight * of the node at position x. The nodes at x and y are then "swapped" in terms * of their position in the list and their parents while maintaining all other * attributes. This process of weight increment and swapping is then repeated * for the parent of the node at position y until the root node is reached. The * operation of the Huffman processor is controlled by the set of parameters * defined by a Huffman Initialization that is uniquely defined (within a CLC) * by the value of the Huffman Initialization ID (HI-ID) specified in the CH. *  * @author Stein Gunnar Bakkeby */
public class HuffmanProcessor {
  /* Field values */
  private ArrayList<HuffNode> tree;
  private boolean updateCharacterSymbols = false;
  private boolean updateControlSymbols   = false;
  private String  init_file;
  private int     charset;
  private int     hp_id = 0;
  private CH previousCH = null;

  private boolean auto_store;
  private int     numberOfProcessedBits = 0;
  
  /* Static field values */
  private static final int MAX_WEIGHT = 0x8000; // 32768
  /* End of static field values */
  
  /**
   * Constructor, creates the Huffman processor based
   * upon a given compression header.
   * 
   * @param ch The compression header
   * @throws IOException If initialisation file cannot be read
   */
  public HuffmanProcessor(final CH ch) throws IOException {
    changeInitialisation(ch);
  }
  
  /**
   * Constructor, creates the HuffmanProcessor based upon
   * the compression header.
   * 
   * @param ch The compression header
   * @throws IOException If initialisation file cannot be read
   */
  public void changeInitialisation(final CH ch) throws IOException {
    if (previousCH == null
        || previousCH.isUpdateNeeded(ch, CH.CHANGE_HUFFMAN_INITIALISATION)) {
      int language = ch.getCLC();
      String lang  = CBS.parse(language).toString().toLowerCase();
      /* If change initialisation ID */
      
      if (ch.getExtensionValue(CH.CHANGE_HUFFMAN_INITIALISATION) != -1)
        hp_id = ch.getExtensionValue(CH.CHANGE_HUFFMAN_INITIALISATION);
      String path = this.getClass().getCanonicalName();
      path = path.substring(0, path.lastIndexOf("."));
      final String resource = path + "."
                            + lang
                            + "_huffman_"
                            + hp_id;
      Settings s = new Settings(resource);
  
      updateCharacterSymbols = s.getBoolean("option_0");
      updateControlSymbols   = s.getBoolean("option_1");
      charset                = s.getInteger("character_set_id");
      
      String file = s.getString("init_file");
      file = file.replace("<id>", "" + hp_id);
      file = file.replace("<cgp>", (ch.isCharacterGroupEnabled() ? "1" : "0"));
      file = file.replace("<lang>", lang);
      this.init_file = file;
      
      HuffNode[] a = readInitFile(file);
      /* If change character set */
      if (ch.getExtensionValue(CH.CHANGE_CHARACTER_SET) != -1) {
        int length = a.length;
        String[] list = new String[length];
        for (int i = 0; i < length; i++) {
          list[i] = changeCharacterSet(
              "" + a[i].getSymbol(),
              charset,
              ch.getExtensionValue(CH.CHANGE_CHARACTER_SET));;
        }
        
        for (int i = 0; i < length; i++) {
          a[i].setSymbol(list[i].charAt(0));
        }
        charset = ch.getExtensionValue(CH.CHANGE_CHARACTER_SET);
      }
      /* Destroy unnecessary leaf nodes. */
      if (charset == 1) { // GSM 7-bit default alphabet
        /* 
         * If the character set specified for compression is the GSM 7
         * bit default alphabet, leaf nodes are not created for the
         * New 8bit Character and the New UCS2 Row symbols.
         */
        a = destroyIfPresent(a, CompressionProcessor.CTRL_SYMB_NEW_8BIT_CHAR);
      }
      if (!CompressionProcessor.isUCS2Enabled()) {
        /*
         * If the character set specified for compression is not UCS2,
         * a leaf node is not created for the New UCS2 Row symbol.
         */
        a = destroyIfPresent(a, CompressionProcessor.CTRL_SYMB_NEW_UCS2_ROW);
      }
      if (!ch.isKeywordEnabled()) {
        /*
         * If the Keyword processor is disabled, no leaf node is created
         * for the Keyword symbol.
         */
        a = destroyIfPresent(a, CompressionProcessor.CTRL_SYMB_KEYWORD);
      }
      this.tree = buildTree(a, false);
    }
    previousCH = new CH(ch);
  }
  
//  
//  /**
//   * This will print the Huffman tree.
//   * 
//   * @param root The root of the tree
//   */
//  public void printTree(HuffNode root) {
//    printNode(root, "");
//    System.out.println("-----------------------------------");
//  }
//  
//  /**
//   * This will print a Huffman node, used by printTree(HuffNode).
//   * 
//   * @param n The node to print
//   * @param bin The current binary value
//   */
//  private void printNode(final HuffNode n, final String bin) {
//    if (n == null) {
//      System.out.println("HuffNode is null"); // T O D O   log
//      return;
//    }
//    if (n.isLeaf()) {
//      System.out.println("Leaf: Symbol = " + n.getSymbol()
//          + ", Weight = " + n.getWeight() + ", Code = " + bin);
//      return;
//    }
//    System.out.println("Node: Symbol = " + n.getSymbol()
//        + ", Weight = " + n.getWeight() + ", Code = " + bin);
//    
//    HuffNode left  = n.getLeft();
//    HuffNode right = n.getRight();
//    
//    if (left != null) {
//      printNode(left, bin + "1");
//    }
//    if (right != null) {
//      printNode(right, bin + "0");
//    }
//  }
  
  private HuffNode[] destroyIfPresent(final HuffNode[] array,
                                      final int symbol) {
    final int length = array.length;
    for (int i = 0; i < length; i++) {
      if (array[i] != null && array[i].getSymbol() == symbol) {
        array[i] = null;
        /* Deletes multiple instances if present, otherwise break here */
      }
    }
    return array;
  }
  
  /**
   * Reads the init file for the Huffman tree.
   * 
   * @return An array of HuffNodes
   */
  public HuffNode[] readInitFile() {
    return readInitFile(init_file);
  }
  
  /**
   * This will set the tree to be used for compression/decompression.
   * 
   * @param tree The Huffman tree
   */
  public void setTree(final ArrayList<HuffNode> tree) {
    this.tree = tree;
  }
  
  /**
   * This will return the Huffman tree.
   * 
   * @return The ArrayList of HuffNodes
   */
  public ArrayList<HuffNode> getTree() {
    return tree;
  }
  
  /**
   * Set this to true to automatically store the tree in
   * the Huffman processor when it is build, updated, and
   * a new node is added.
   * 
   * @param value True if tree is to be automatically stored, false otherwise
   */
  public void setAutoStore(final boolean value) {
    auto_store = value;
  }
  
  /**
   * Indicates whether the Huffman tree is automatically stored
   * when the tree is build, stored, and a new node is added.
   * 
   * @return True if the tree is automatically stored upon build and update
   */
  public boolean getAutoStore() {
    return auto_store;
  }
  
  /**
   * Reads a given init file for the Huffman tree.
   * 
   * @param file File containing frequency information
   * @return An array of HuffNodes
   */
  public HuffNode[] readInitFile(final String file) {
    final CSVReader reader = new CSVReader(
        ClassLoader.getSystemResourceAsStream(file), true);
    reader.setBufferSize(128);
    reader.read();
    final String[][] dat = reader.getCSV();
    final int columns    = reader.getNumberOfColumns();
    final int rows       = reader.getNumberOfRows();
    final HuffNode[] a   = new HuffNode[rows];
    int col_symb, col_wght;
    switch (columns) {
    case 1:
      col_symb = 0;
      col_wght = -1;
      break;
      
    case 2:
     col_symb = 0;
     col_wght = 1;
     break;
     
    case 3:
      col_symb = 1;
      col_wght = 2;
      break;
      
    default:
      if (columns > 3) {
        col_symb = 1;
        col_wght = 2;
      } else {
        return new HuffNode[0];
      }
    }
    
    int t_val = 0;
    if (col_wght == -1) {
      for (int i = 0; i < rows; i++) {
        int val = -1;
        final String s = dat[col_symb][i];
        try {
          val = Integer.parseInt(s);
        } catch (NumberFormatException e) {
          if (s.length() > 0) val = s.charAt(0); 
        }
        a[i] = (val == -1 ? null : new HuffNode((char) val, 1));
      }
      t_val = rows;
    } else {  
      for (int i = 0; i < rows; i++) {
        int s_val = -1;
        int w_val = -1;
        final String s = dat[col_symb][i];
        final String w = dat[col_wght][i];
        try {
          w_val = Integer.parseInt(w); 
          s_val = Integer.parseInt(s);
        } catch (NumberFormatException e) {
          if (s.length() > 0) s_val = s.charAt(0);
          if (w_val == -1) w_val = 1;
        }
        t_val += w_val;
        a[i] = (s_val == -1 ? null : new HuffNode((char) s_val, w_val));
      }
    }
    return a;
  }
  
  /**
   * This will write the Huffman tree data to a file with a given name.
   * 
   * @param filename The file to write to
   * @return True if file was created successfully, false otherwise
   */
  public boolean writeInitFile(final String filename) {
    try {
      final File f = new File(filename);
      if (!f.exists()) {
        if (!f.createNewFile()) return false;
      }
      if (!f.canWrite()) return false;
      int size = tree.size();
      final ArrayList<HuffNode> copy = new ArrayList<HuffNode>();
      copy.addAll(tree);
      for (int i = 0; i < copy.size(); i++) {
        final HuffNode n = copy.get(i);
        if (!n.isLeaf()) {
          copy.remove(i);
          i--;
        }
      }
      size = copy.size();
      final String[][] csv = new String[2][size];
      for (int i = 0; i < size; i++) {
        final HuffNode n = copy.get(i);
        csv[0][i] = "" + n.getSymbol();
        csv[1][i] = "" + n.getWeight();
      }
      final CSVWriter writer = new CSVWriter(new FileOutputStream(f));
      writer.setLabels(new String[] {"Symbol", "Weight"});
      writer.write(csv, 2, size);
      writer.close();
      return true;
    } catch (IOException e) {
      UTIL_DEBUG.log(e);
      return false;
    }
  }

  /**
   * This will build the tree based on an array of Huffman tree nodes.
   * 
   * @param array The array of Huffman tree nodes
   * @param rescale A Boolean value indicating whether frequencies need
   *                to be rescaled as a result of the root node weight
   *                becoming the maximum value.
   * @return A completed Huffman tree
   */
  public ArrayList<HuffNode> buildTree(HuffNode[] array,
                                       final boolean rescale) {
    /* Step 1: Sort array, and rescale if needed */
    int length = array.length;
    final ArrayList<HuffNode> list = new ArrayList<HuffNode>();

    for (int i = 0; i < length; i++) {
      if (array[i] != null) {
        for (int j = i + 1; j < length; j++) {
          if (array[j] != null && array[i].getWeight() > array[j].getWeight()){
            HuffNode tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
          }
        }
        if (rescale) array[i].setWeight((array[i].getWeight() + 1)/2);
        list.add(array[i]);
      }
    }
    
    /* Step 2 */
    HuffNode joinLeft  = null;
    HuffNode joinRight = null;
    HuffNode newNode   = null;
    
    boolean isRoot;
    int size;
    final ArrayList<HuffNode> copy = new ArrayList<HuffNode>();
    copy.addAll(list);
    for (int currentNode = 0; currentNode + 1 < copy.size(); ) {
      joinLeft  = copy.get(currentNode);
      joinRight = copy.get(currentNode + 1);
      copy.remove(0);
      copy.remove(0);
      int weight = joinLeft.getWeight() + joinRight.getWeight();
      newNode = new HuffNode();
      newNode.setLeft(joinLeft);
      newNode.setRight(joinRight);
      newNode.setWeight(weight);
      size = copy.size();
      isRoot = true;
      for (int i = 0; i < size; i++) {
        if (copy.get(i).getWeight() > weight) {
          copy.add(i, newNode);
          list.add(newNode);
          isRoot = false;
          break;
        }
      }
      if (isRoot) {
        copy.add(newNode);
        list.add(newNode);
      }
    }
    /* And sort again */
    ArrayList<HuffNode> ret = new ArrayList<HuffNode>();
    // TODO reconsider using a different variable than overriding array
    array = list.toArray(new HuffNode[list.size()]);
    length = array.length;
    for (int i = 0; i < length; i++) {
      if (array[i] != null) {
        for (int j = i + 1; j < length; j++) {
          if (array[i].getWeight() > array[j].getWeight()){
            HuffNode tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
          }
        }
      }
      ret.add(array[i]);
    }
    if (auto_store) this.tree = ret;
    return ret;
  }
  
  /**
   * This will update the tree.
   * 
   * @param symbol The symbol whose frequency is to be incremented by 1
   * @param tree The tree to update
   * @return The updated tree
   */
  public ArrayList<HuffNode> updateTree(final int symbol,
                                        ArrayList<HuffNode> tree){
    HuffNode root = tree.get(tree.size() - 1);
    if (root.getWeight() + 1 > MAX_WEIGHT) {
      tree = buildTree(tree.toArray(new HuffNode[tree.size()]), true);
    }
    HuffNode current = null;
    int size = tree.size();
    int i;
    for (i = 0; i < size; i++) {
      if (tree.get(i).getSymbol() == symbol) { // expect only 1 symbol in tree
        current = tree.get(i);
        current.setWeight(current.getWeight() + 1);
        break;
      }
    }
    if (current != null) {
      HuffNode t; // temporary node
      for (i++; i < size; i++) {
        t = tree.get(i);
        if (current.equals(t.getLeft()) || current.equals(t.getRight())) {
          t.setWeight(t.getWeight() + 1);
          current = t;
        }
      }
      /* Sort list */
      int length = tree.size();
      HuffNode[] array = tree.toArray(new HuffNode[length]);
      tree = new ArrayList<HuffNode>();
      for (int j = 0; j < length; j++) {
        for (int k = j + 1; k < length; k++) {
          if (array[k].getWeight() < array[j].getWeight()) {
            HuffNode tmp = array[j];
            array[j] = array[k];
            array[k] = tmp;
          }
        }
        tree.add(array[j]);
      }
    }
    if (auto_store) this.tree = tree;
    return tree;
  }
  
  /**
   * This will add a symbol to the tree.
   * 
   * @param symbol The symbol to add
   * @param tree The tree in which the symbol is to be added
   * @return The updated tree
   */
  public ArrayList<HuffNode> addNode(final int symbol,
                                     ArrayList<HuffNode> tree) {
    final HuffNode lhtNode = tree.get(0);
    final HuffNode newNode = new HuffNode();
    final HuffNode newLeaf = new HuffNode(symbol, 0);
    final int size = tree.size();
    HuffNode t; // temporary node
    for (int i = 0; i < size; i++) {
      t = tree.get(i);
      if (lhtNode.equals(t.getLeft())) {
        t.setLeft(newNode);
        break;
      }        
      if (lhtNode.equals(t.getRight())) {
        t.setRight(newNode);
        break;
      }
    }
    newNode.setRight(lhtNode);
    newNode.setLeft(newLeaf);
    newNode.setWeight(lhtNode.getWeight());
    tree.add(0, newNode);
    tree.add(0, newLeaf);
    tree = updateTree(symbol, tree);
    if (auto_store) this.tree = tree;
    return tree;
  }
  
  /**
   * This will compress a symbol and return a bitstream.
   * 
   * @param symbol The symbol to compress
   * @return The Huffman bitstream
   */
  public IntArrayBuilder compress(final int symbol) {
    final IntArrayBuilder output = new IntArrayBuilder();
    int sourceSymbol = symbol;
    /* Step 1 */
    int size = tree.size();
    HuffNode t; // temporary node
    HuffNode currentNode = null;
    boolean noLeafNode = true;
    int i;
    for (i = 0; i < size; i++) {
      t = tree.get(i);
      if (t.getSymbol() == symbol) {
        currentNode = t;
        noLeafNode = false;
        break;
      }
    }
    if (noLeafNode) {
      sourceSymbol = (symbol > 127
                   ? CTRL_SYMB_NEW_8BIT_CHAR
                   : CTRL_SYMB_NEW_7BIT_CHAR);
      for (i = 0; i < size; i++) {
        t = tree.get(i);
        if (t.getSymbol() == sourceSymbol) {
          currentNode = t;
          noLeafNode = false;
          break;
        }
      }
    }
    
    /* Step 2 */
    IntArrayBuilder bin = new IntArrayBuilder();
    for (; i < size; i++) {
      t = tree.get(i);
      if (currentNode.equals(t.getLeft())) {
        bin.append(1);
        currentNode = t;
      } else 
      if (currentNode.equals(t.getRight())) {
        currentNode = t;
        bin.append(0);
      }
    }
    /* Step 3 */
    size = bin.length();
    for (i = 0; i < size; i++) output.append(bin.intAt(size - 1 - i));
    /* Step 4 */
    if (sourceSymbol != symbol) {
      bin.append(Convert.intToIntArray(symbol, 8));
      output.append(bin.substring(bin.length() - 7));
      tree = addNode(symbol, tree);
    } else {
      /* Step 5 */
      if (symbol < 256 && updateCharacterSymbols) {
        tree = updateTree(symbol, tree);
      } else {
        /* Step 6 */
        if (symbol >= 256 && updateControlSymbols) {
          tree = updateTree(symbol, tree);
        }
      }
    }
    return output;
  }
  
  /**
   * This will decompress a bitstream.
   * 
   * @param bitstream The bitstream
   * @return The decoded symbol
   */
  public int decompress(final IntArrayBuilder bitstream) {
    int size = bitstream.length();
    int output = 0;
    HuffNode currentNode = tree.get(tree.size() - 1);
    /* Step 1 */
    int i;
    for (i = 0; i < size; i++) {
      currentNode = (bitstream.intAt(i) == 1 ? currentNode.getLeft()
                                             : currentNode.getRight());
      if (currentNode.isLeaf()) break;
    }
    numberOfProcessedBits = i + 1;

    int symbol = currentNode.getSymbol();
    /* Step 2 */
    if (symbol == CompressionProcessor.CTRL_SYMB_NEW_7BIT_CHAR
     || symbol == CompressionProcessor.CTRL_SYMB_NEW_8BIT_CHAR) {
      IntArrayBuilder bin = bitstream.substring(i + 1, i + 8);
      numberOfProcessedBits += 7;
      if (symbol == CompressionProcessor.CTRL_SYMB_NEW_8BIT_CHAR) {
        bin.insert(0, 1);
      }
      output = Convert.binToInt(bin);
      tree = addNode(output, tree);
    } else {
      /* Step 3 */
      output = symbol;
      /* Step 4 */
      if (output < 256 && updateCharacterSymbols) {
        tree = updateTree(output, tree);
      } else {
        /* Step 5 */
        if (output >= 256 && updateControlSymbols) {
          tree = updateTree(output, tree);
        }
      }
    }
    return output;
  }

  /**
   * This will return the number of processed bits.
   * 
   * @return Integer
   */
  public int getNumberOfProcessedBits() {
    return numberOfProcessedBits;
  }
}